1. Field of the Invention
The invention relates to a method and apparatus for information processing, particularly to a memory allocation system.
2. Background Art
In the prior art, information relating to memory allocation is not stored in a manner that allows it to be examined by processes external to the allocator. The ability to examine this information is desirable since an understanding of the overall configuration of allocated memory space and free memory space is useful for evaluating and optimizing performance of a computer system especially when concerned with applications that exist for long periods of time (e.g. greater than five minutes). Desktop applications often exist for periods of time measured in months. To examine how memory is being allocated for particular code in the prior art, it is necessary to modify that code before it is executed. Thus, the code being executed is not identical to the code for which the information relating to memory allocation is sought.
Prior Art Techniques
Computers are used to process information. Computers execute programs that specify steps to be used to process the information. A computer operating system controls execution of the programs. Some computer operating systems allow multiple programs to be executed concurrently. In such operating systems, multiple processes are established that allow execution of the multiple programs. The operating system allocates the processing time of a processor to the processes. Program information and data processed by the programs are stored in memory devices of the computer. When the execution of a program begins, memory space in the memory devices is allocated to the corresponding process. If an inadequate amount of memory space is allocated to a process, the process may encounter a fatal out-of-space condition when running. When the execution of a program ends, the memory space allocated to the process is freed to allow the memory space to be reused.
Techniques are needed to allocate memory space to a process and to free or deallocate the memory space after the process no longer needs it. In the past, in the C programming language, standardized C library routines were provided to allow memory space to be allocated and freed. The standard C library routine to allocate memory space is referred to as the xe2x80x9cmallocxe2x80x9d function. The standard C library routine to free memory space if referred to as the xe2x80x9cfreexe2x80x9d function.
The xe2x80x9cmallocxe2x80x9d function is executed with a parameter specifying the size of the memory block to be allocated. The xe2x80x9cmallocxe2x80x9d function finds a block of memory space of adequate size and returns a pointer to the beginning of the memory block.
The xe2x80x9cfreexe2x80x9d function is executed with a parameter specifying a pointer pointing to a memory block previously allocated by the xe2x80x9cmallocxe2x80x9d function. The xe2x80x9cfreexe2x80x9d function frees the specified memory block to be used again by the same process.
The xe2x80x9cmallocxe2x80x9d function maintains multiple lists of free blocks according to size and allocates space from the appropriate list. If xe2x80x9cmallocxe2x80x9d is unable to locate an unallocated memory block of sufficient size, it invokes an xe2x80x9csbrkxe2x80x9dfunction to have the operating system provide more memory space from which allocations may be made.
If it is desired to change the size of a memory block that has already been allocated, the xe2x80x9creallocxe2x80x9d function may be invoked. The xe2x80x9creallocxe2x80x9d function is executed with a parameter specifying the pointer that points to a memory block that has already been allocated and another parameter specifying the new size desired for that memory block. The xe2x80x9creallocxe2x80x9d function allocates a memory block of sufficient size and returns a pointer to the new memory block. The pointer may point to a memory block having the same beginning location as the memory block that existed at the time the xe2x80x9creallocxe2x80x9d function was called, or the pointer may point to a memory block having a different beginning location if inadequate memory space existed in the memory block previously allocated and free memory space contiguous with that memory block.
While the xe2x80x9cmallocxe2x80x9d and xe2x80x9cfreexe2x80x9d functions are adequate for obtaining and freeing blocks of memory, they do not provide the ability to examine the current status of free and allocated memory space. This ability is desirable since an understanding of the overall configuration of allocated memory space and free memory space would be useful for evaluating and optimizing performance of a computer system, especially in long-lived processes. In particular, it would be useful to be able to specify a process and be provided with information indicating the blocks of memory space allocated to the process and their locations in the overall memory space of the computer system.
In the past, a program could be rewritten to include calls to a xe2x80x9cmallinfoxe2x80x9d function. The xe2x80x9cmallinfoxe2x80x9d function provides information describing memory space allocation. Typical information provided by the xe2x80x9cmallinfoxe2x80x9d function includes the total space in the arena, the number of ordinary blocks, the number of small blocks, the number of holding blocks, the space in holding block headers, the space in small blocks in use, the space in free small blocks, the space in ordinary blocks in use, the space in free ordinary blocks, cost of enabling the keep option, the maximum size of small blocks, the number of small blocks in a holding block, the small block rounding factor, the space (including overhead) allocated in ordinary blocks, the number of ordinary blocks allocated, and the number of bytes used in maintaining the free tree. While this information is useful for analyzing performance, the calls to the xe2x80x9cmallinfoxe2x80x9d function must be added to the program being analyzed. Thus, use of the xe2x80x9cmallinfoxe2x80x9d function is an invasive procedure that does not permit analysis of a program in the form in which the program is intended to be used.
The inclusion of the xe2x80x9cmallinfoxe2x80x9d function adds complexity to the code which increases development and maintenance costs. Further, the memory space allocation information associated with a process that includes the xe2x80x9cmallinfoxe2x80x9d functionality may be skewed by the inclusion of the xe2x80x9cmallinfoxe2x80x9d function. That is, the xe2x80x9cmallinfoxe2x80x9d functionality may alter the memory allocation information. This alteration may result in difficulty in making a memory allocation assessment by an application developer.
To include the xe2x80x9cmallinfoxe2x80x9d functionality in a process executing code that does not include this functionality, it is necessary to terminate the process and initiate a new process executing code that contains calls to the xe2x80x9cmallinfoxe2x80x9d function. Thus, it is cumbersome to add this functionality to code that is already executing.
The invention provides a method and apparatus for noninvasively providing information relating to memory space allocation. The invention allows memory space allocation to be examined by processes external to the memory space allocator without the need to modify the code for processes to which memory space is being allocated.
An embodiment of the invention provides a method and apparatus for maintaining memory allocation information comprising the steps of reserving a memory space arena, defining a data structure to store the memory allocation information, and storing the memory allocation information.
The memory allocation information comprises a first value representative of a quantity of pages of a first bucket size instantiated in the memory space arena. The memory allocation information also comprises a second value representative of a quantity of buckets allocated in one of the quantity of pages of the first bucket size instantiated in the memory space arena. The memory allocation information further comprises a pointer to a linked list identifying unallocated buckets in one of the quantity of pages of the first bucket size.instantiated in the memory space arena.
One embodiment of the invention also provides a method and apparatus to modify the memory allocation information when a change in memory allocation occurs. The invention allows the memory allocation information to be modified appropriately when memory is allocated and when memory is freed.
An embodiment of the invention provides a method and apparatus to identify the data structure by storing a data structure identifier in the data structure. The data structure identifier is preferably a known or readily identified value stored in a known or readily identified memory location within the data structure. The memory location at which the data structure identifier is stored is intentionally made known to external programs, thereby allowing the external programs to know where to look for the data structure identifier and to know what to look for at that memory location so as to identify the data structure.